NC Milling
Simulating numerically controlled (NC) milling is of fundamental importance in computer aided design (CAD) and computer aided manufacturing (CAM). During simulation, a computer model of a workpiece is edited with a computer representation of an NC milling tool and a set of NC milling tool motions to simulate the milling process.
The workpiece model and tool representation can be visualized during the simulation to detect potential collisions between parts, such as the workpiece and the tool holder, and after the simulation to verify the final shape of the workpiece.
The final shape of the workpiece is affected by the selection of the tool and the tool motions. Instructions for controlling the motions are typically generated using the CAM system from a graphical representation of the desired final shape of the workpiece. The motions are typically implemented using numerical control programming language, also known as preparatory code or G-Codes, see, e.g., the RS274D and DIN 66025/ISO 6983 standards.
The G-Codes generated by the CAM system may not produce an exact replication of the desired shape. In addition, the movement of the NC tool is governed by operational parts of the NC milling machine, which can have constrained speeds, ranges of motion, and abilities to accelerate and decelerate. Therefore, the actual tool motions may not exactly follow the NC machine instructions.
Discrepancies between the final shape of the workpiece and the desired shape of the workpiece may be very small. In some situations, these discrepancies can result in undesirable gouges or nicks in the surface of the final shape of the workpiece with sizes on the order of a few micrometers in depth and width, and tens of micrometers in length.
Typically, a set of NC machine instructions is tested by milling a test workpiece made of a softer, less expensive material prior to milling the desired part. If visual inspection of the test workpiece locates undesirable discrepancies in the test workpiece, the NC machine instructions can be modified accordingly.
This manual testing is time consuming and expensive. Time for machining a single test workpiece may be on the order of hours and several iterations may be required before an acceptable set of NC machine instructions is attained. Thus, it is desirable to test for these discrepancies using computer-based simulation and rendering. However, in order to detect discrepancies with dimensions on the order of a few micrometers for workpieces, which may have dimensions on the order of one meter, very precise computer models are required. It is an object of the present invention to provide a space and time efficient method for representing and rendering such high precision models for milling simulation.
Swept Volumes
During milling, the tool moves relative to the workpiece according to a prescribed tool motion, referred to herein as a tool path. The tool path can contain information about the relative position, orientation, and other shape data of the tool with respect to the workpiece.
As the tool moves along the tool path, the tool carves out a “swept volume.” During milling, as the tool moves along the tool path, a portion of the workpiece that is intersected by the swept volume is removed. This material removal can be modeled computationally as a constructive solid geometry (CSG) difference operation, in which the portion of the workpiece is removed from the workpiece using a CSG subtraction operation of the swept volume from the workpiece.
Although NC milling simulation is used as an example application, swept volumes have applications in many areas of science, engineering, entertainment, and computer graphics. Some specific applications include computer-aided design, freeform design, computer-based drawing, animation, solid modeling, robotics, manufacturing automation, and visualization to name but a few. The following description applies to all areas where an accurate representation of a swept volume is required, or desired.
Although this description focuses on three-dimensional coordinate systems, the term ‘swept volume’ can be extended more generally to N-dimensional coordinate systems. In particular, the following description also applies to areas swept out by a one-dimensional or two-dimensional shape moving along a path in a two-dimensional space, or to a hyper-volume swept out by a shape moving over a path or surface in higher dimensional systems.
An overview of the importance and challenges in swept volume research is presented by Abdel-Malek, Blackmore, and Joy in “Swept Volumes: Foundations, Perspectives, and Applications”, International Journal of Shape Modeling, 2006. They conclude that research in this field is limited by the difficulty of implementing complex mathematical formulations of swept volumes using software, and that computing the boundaries of swept volumes remains a challenging problem requiring better visualization tools and more accurate methods.
The swept volumes of simple shapes moving along simple paths can sometimes be represented analytically, as described in U.S. Pat. No. 4,833,617. However, those methods do not generalize to complex shapes and complex tool paths.
Several methods approximate the swept volumes of polygonal shapes. Models of polygonal shapes can be encoded in a spatial hierarchy for efficient editing via CSG operations as in “Interactive CSG” Proceedings, Technical Sketches, SIGGRAPH, 1999, Butcher, or for efficient collision detection as in U.S. Pat. No. 6,099,573. A method for approximating the swept volume of a polygonal object is also described in “Computing Swept Volumes”, Journal of Visualization and Animation, 2000, Abrams and Allen.
U.S. Pat. No. 6,862,560 describes a method for simulating machining using CSG operations on polygonal models of swept volumes. In that method, the boundary of the workpiece is encased in a set of cells, where each cell includes references to swept volume polygons that intersect the cell. Intersections between the workpiece and the swept volume polygons within a particular cell can be processed, on demand, to generate a high precision rendering of the milled surface for a small region of interest. However, visualizing the full model at high precision is extremely time consuming.
U.S. Pat. No. 6,993,461 describes representing an object as a polyhedron. The object is placed along the path at discrete time steps using a series of transformations. Edges and faces of the polyhedral representation that are on the boundary of the swept volume are determined at each time step and connected to each other to generate a polyhedral approximation of the swept volume.
The accuracy of each of those polygonal methods is limited by the polygonal representation of the object model. Billions of polygons may be required to accurately represent the curved surface of a complex tool, especially if the radius of curvature is small. Thus, those methods may either have limited accuracy or have prohibitive processing times and memory requirements for generating high precision models of swept volumes, or both. In addition, methods that approximate the swept volume as a series of discrete time steps have limited precision between the discrete time steps, and are subject to aliasing artifacts.
Another common representation for milling simulation is known as the Z-buffer or a Dexel method. That method is described in “Real-time Shaded NC Milling Display”, Proceedings, SIGGRAPH 1986, van Hook. U.S. Pat. No. 7,149,668 describes a similar method in which the workpiece is modeled by a grid of straight lines all in the z-direction, and the milling simulation is performed by moving the tool model over the grid and modifying the height of the lines representing the workpiece that are intersected by the tool.
The Dexel method typically suffers from limited resolution, especially in directions not aligned with the z-axis, and is not suitable for generating high precision models of swept volumes. The Dexel representation is related to voxel-based representations. In “Volume Visualization”, IEEE Computer Society Press, 1991, Kaufman describes voxel-based representations as well as methods for rendering and processing voxel-based representations. “Sculpting: an Interactive Volumetric Modeling Technique”, Proceedings, SIGGRAPH 1991, Galyean and Hughes, and “Volume Sculpting: Proceedings, SIGGRAPH 1995, Wang and Kaufman, both simulate sculpting using CSG operations on voxel-based representations of objects.
Methods that use binary voxels to represent swept volumes are described in U.S. Pat. No. 6,044,306, and “Method and Apparatus for Shaping Geometric Shapes” and “Octree-based Boundary Evaluation for General Sweeps”, Proceedings, TMCE, 2008 Erdim and Ilies. The accuracy of those methods is limited by the size of the smallest voxel used to represent the swept volumes.
Distance Fields
Distance fields are an effective representation for rendering and editing shapes, as described in U.S. Pat. Nos. 6,396,492, 6,724,393, 6,826,024, and 7,042,458.
Distance fields are a form of implicit functions that represent an object. A distance field is a scalar field that gives a shortest distance to the surface of the object from any point in space. A point at which the distance field is zero is on the surface of the object. The set of points on the surface of the object collectively describe the boundary of the object, also known as the d=0 isosurface. Generally, the distance field of an object is positive for points inside the object, and a negative for points outside the object, although the sign can be inverted.
Distance fields have been used to represent and render swept volumes. “Sweeping of Three Dimensional Objects”, Computer Aided Design, 20(4), 1990, Martin and Stephenson, described a theoretical foundation for defining the envelope of a swept volume in terms of an implicit function. In “Function Representation for Sweeping by a Moving Solid”, Proceedings, Solid Modeling, 1995, Sourin and Pasko represented swept volumes using implicit surfaces. However, implicit surfaces can be difficult to render, and a suitable implicit representation for an arbitrarily complex tool shape is difficult to define.
A procedure for computing the distance field of an object is called a distance field function. For very simple objects, such as a plane, a sphere or a cylinder, the distance field function can be an analytic function with a closed form. For more complex objects the analytic function may impossible. However, a numerical procedure can still be possible. For example, U.S. Pat. No. 2010/0298967 describes a numerical procedure for determining the distance field of a swept object, such as a swept milling tool.
Adaptively sampled distance fields (ADFs) use detail-directed sampling to provide a much more space and time efficient representation of distance fields than is obtained using regularly sampled distance fields. ADFs store the distance field as a spatial hierarchy of cells. Each cell contains distance data and a reconstruction method for reconstructing a portion of the distance field associated with the cell. Distance data can include the value of the distance field, as well as the gradient and partial derivatives of the distance field. The distance field within a cell can be reconstructed as needed to reduce memory and computational complexity.
ADFs can be used to simulate editing using CSG operations. The model to be edited and the editing tool can be represented as distance functions, regularly sampled distance fields, or ADFs. The editing process can generate the ADF of the edited shape explicitly, for example by modifying the ADF of the model.
Alternatively, the edited shape can be represented implicitly as a composite ADF (CADF). The CADF is generated to represent the object, where the CADF includes a set of cells arranged in the spatial hierarchy. Each cell in the CADF includes a subset of the set of geometric element distance field functions and a reconstruction method for combining the subset of geometric element distance field functions to reconstruct a composite distance field of a portion of the object represented by the cell. Each distance field in the subset of distance fields forms a part of the boundary of the object within the cell, called the composite boundary.
CADFs can reconstruct the distance field of a milled object with a very high accuracy. The distance field function of the set of geometric elements can be computed with high accuracy by analytic or numerical methods, and values of the distance field functions can be combined with high accuracy. The resulting surface is very detailed with surface features that may be smaller than 1 micron for a simulated object that is about one cubic meter.
Geometric Properties of Removed Volume
During milling, as the NC milling tool moves along the tool path, the tool can be in contact with the workpiece. As the tool moves relative to the workpiece, the tool generates the swept volume. A portion of the workpiece that is intersected by the swept volume is removed, and is a “removed volume.” The workpiece that is updated by the removed volume is an “in-process workpiece.”
The simulation of the milling requires an accurate modeling of the material removed by the milling tool due to each tool movement. Accordingly, there is a need to determine the removed volume or an accurate geometric representation of the removed volume.
Currently, Computer Aided Design (CAD)/Computer Aided Manufacturing (CAM) systems that generate tool path information employ the geometric and volumetric analysis to select parameters of a simulation. Average milling forces are assumed to be proportional to the material removal rate (MRR) during any particular instant. The removed volume is divided by a tooth passing frequency of milling tool to determine the average MRR for each tool movement, where the tooth passing frequency is the frequency of a teeth that engages with the workpiece and obtained by multiplying the number of teeth of milling tool and spindle speed.
Average milling forces are analyzed using the MRR determined from removed volume, and the power required to mill the material is proportional to the MRR. Spindle power and specific energy consumed in removing a unit volume of material can also be used in order to increase the performance of the machining. In addition computing the removed volume, other geometric properties of removed volume, such as mass, center of mass, surface area, moment of inertia, length, width and thickness can also be computed to use for process analysis. The moment of inertia of the removed volume is used for estimating the stresses applied by the milling tool to the workpiece, and later estimating the residual stresses left on the machined surface.
Volume computation of solid bodies is fundamental to many geometric applications. An overview of the importance and challenges in volume computation is described by Lee and Requicha in “Algorithms for computing the volume and other integral properties of solids. I. Known methods and open issues,” Communications of the ACM, 1982. Determining accurate moments and volumes of solids removed by milling tool along the tool path is difficult due to the presence of curved freeform surfaces. Therefore, the volumes are currently being computed by commercial software by first evaluating and tessellating the surfaces and computing the volumes of the tessellated objects as described in “ACIS Geometric Modeler: User Guide v20.0,” 2009, Spatial Corporation.
Another common method for volume calculation is converting the volume integrals to surface integrals by using a divergence theorem. That approach is described by Gonzalez-Ochoa, McCammon and Peters in “Computing moments of objects enclosed by piecewise polynomial surfaces,” Journal ACM Transactions on Graphics, 1998. Polyhedral approximations indicate that accurate evaluation of integral properties of curved objects via polyhedral approximations may require the use of polyhedral with a large number of faces. Numerical integration techniques are used to evaluate surface integrals of for a given polyhedral approximation. However, one of the main limitations is the level of tessellation in order to guarantee the accuracy of result.
Cellular approximations by using regular or octree subdivision are related to voxel-based representations, and these methods have accuracy and memory limited by the size of the smallest voxel used to represent the removed volume. For example, one method uses recursive subdivision surfaces as described by Peters and Nasri in “Computing Volumes of Solids Enclosed by Recursive Subdivision Surfaces,” EUROGRAPHICS 1997. That method computes the volume by estimating the volume of the local convex hull near extraordinary point. However the close-form representation of implicit, explicit or parametric forms is not always available, especially in NC milling case.
Several methods determine the geometric properties of solids using GPUs (Graphic Processing Units) for solids represented by NURBS (Non-Uniform Rational B-Spline) surfaces. Those methods include a method described by Kim, Kim, Ko and Terzopoulos in “Fast GPU computation of the mass properties of a general shape and its application to buoyancy simulation.” The Visual Computer International Journal of Computer Graphics, 2006, and a method described by Krishnamurthy and McMains in “Accurate GPU-accelerated surface integrals for moment computation,” Computer Aided Design Journal, 2011. Although NURBS surfaces are used for high degree of freedom of modeling with smooth continuity of differential properties, the used Boolean operations do not provide accurate result for NC milling simulation systems.
Thus there is a need a method for determining and analyzing the removed volume to be used for a simulation of machining the workpiece by the tool.